-module( octree ).
-export ( [ build/4, walkPoint/3, walkBox/4, walkAllLeafs/3 ] ).


build( { {MinX, MinY, MinZ}, {MaxX, MaxY, MaxZ} }, {CellSizeX, CellSizeY, CellSizeZ }, LeafFunc, AuxParam ) ->
  L = [
    { 1, MinX, MaxX, CellSizeX },
    { 2, MinY, MaxY, CellSizeY },
    { 3, MinZ, MaxZ, CellSizeZ } ],
  splitBox( L, [], [], LeafFunc, AuxParam ).



splitBox( [H|T], Acc, LeafBounds, LeafFunc, AuxParam ) ->
  { Coord, Min, Max, Cell } = H,
  if
    ( Max - Min > Cell ) ->
      Mid = 0.5 * ( Max + Min ),
      { Node1, Aux1 } = splitBox( T, [ { Coord, Min, Mid, Cell } | Acc ], LeafBounds, LeafFunc, AuxParam ),
      { Node2, Aux2 } = splitBox( T, [ { Coord, Mid, Max, Cell } | Acc ], LeafBounds, LeafFunc, Aux1 ),
      Node = { node, Coord, Mid, Node1, Node2 },
      { Node, Aux2 };
      
    true ->
      splitBox( T, Acc, [ { Coord, Min, Max } | LeafBounds ], LeafFunc, AuxParam )
  end;

splitBox( [], [], LeafBounds, LeafFunc, AuxParam ) ->
  { Leaf, Aux } = LeafFunc( listToAabb( LeafBounds ), AuxParam ),
  { { leaf, Leaf }, Aux };

splitBox( [], Acc, LeafBounds, LeafFunc, AuxParam ) ->
  splitBox( lists:reverse( Acc ), [], LeafBounds, LeafFunc, AuxParam ).



listToAabb( L ) -> listToAabb( L, geom:zeroBox() ).
listToAabb( [], B ) -> B;
listToAabb( [ { 1, Min, Max } | T ], { {_MinX, MinY, MinZ}, {_MaxX, MaxY, MaxZ} } ) -> listToAabb( T, { {Min, MinY, MinZ}, {Max, MaxY, MaxZ} } );
listToAabb( [ { 2, Min, Max } | T ], { {MinX, _MinY, MinZ}, {MaxX, _MaxY, MaxZ} } ) -> listToAabb( T, { {MinX, Min, MinZ}, {MaxX, Max, MaxZ} } );
listToAabb( [ { 3, Min, Max } | T ], { {MinX, MinY, _MinZ}, {MaxX, MaxY, _MaxZ} } ) -> listToAabb( T, { {MinX, MinY, Min}, {MaxX, MaxY, Max} } ).



walkPoint( { node, Coord, Mid, N1, N2 }, P, F ) ->
  Q = element( Coord, P ),
  if
    Q < Mid -> walkPoint( N1, P, F );
    true    -> walkPoint( N2, P, F )
  end;
  
walkPoint( { leaf, Value }, _P, F ) ->
  F( Value ).



walkBox( { node, Coord, Mid, N1, N2 }, B={BMin, BMax}, F, Acc ) ->
  Qmin = element( Coord, BMin ),
  Qmax = element( Coord, BMax ),
  A = if
    ( Qmin < Mid ) -> walkBox( N1, B, F, Acc );
    true -> Acc
  end,
  if
    ( Qmax > Mid ) -> walkBox( N2, B, F, A );
    true -> A
  end;
  
walkBox( { leaf, Value }, _B, F, Acc ) ->
  F( Value, Acc ).



walkAllLeafs( { node, _Coord, _Mid, N1, N2 }, F, Acc ) ->
  A = walkAllLeafs( N1, F, Acc ),
  walkAllLeafs( N2, F, A );

walkAllLeafs( { leaf, Value }, F, Acc ) ->
  F( Value, Acc ).
